//! A flexible large number represent type.

#[path = "mods/utils.rs"]
#[macro_use]
mod comparator;

use crate::mods::calculator::*;
use crate::mods::jacobi::jacobi;
use crate::mods::utils::*;
use crate::sieve::Sieve;
use rand::prelude::*;
use rayon::prelude::*;
use std::cmp::{Ordering, PartialEq, PartialOrd};
use std::fmt;
use std::mem::{size_of, transmute};
use std::ops::*;

/// A flexible large number represent type.
///
/// # Examples
///
/// ```rust
/// use integer::prelude::*;
///
/// let zero = Integer::zero();
/// let zero_with_bit_length = Integer::new(2048);
/// assert_eq!(zero_with_bit_length.nblocks(), 1);
/// assert_eq!(zero_with_bit_length.alloc_size(), 32);	// 64bits per block
///
/// let u8_max = Integer::from("ff");
/// ```
///
/// The [`int!`] macro is provided to make initialization more convenient,
/// which internally invoke function [`try_convert`]:
///
/// ```rust
/// use integer::prelude::*;
///
/// let u8_max_1 = int!(0xff);
/// let u8_max_2 = Integer::try_convert(0xff, 1);
/// assert_eq!(u8_max_1, u8_max_2);
/// ```
/// You can also convert numbers from slice, the function will read numbers with little-endian
/// style:
///
/// ```rust
/// use integer::prelude::*;
///
/// let a = Integer::try_convert([128u64, 128], 1);
/// let b = Integer::try_convert([128u32, 0, 128, 0], 1);
/// assert_eq!(a, b);
/// ```
///	Besides, [`random`] function helps to produce the given bit length random number, and even more, [`random_prime`] function
/// creates primes with custom precision(1..100):
///
/// ```rust
/// use integer::prelude::*;
///
/// let a = Integer::random(2048);
/// let b = Integer::random_prime(2048, 100);
/// assert!(b.is_prime(100));
/// ```
///
/// # Slicing and Indexing
///
/// Integer type allows to query the immutable raw value by both indexes and ranges.
/// Because of the basic structure of Integer, indexing result will represents the last N-th 64bit
/// value of the number. if the index is larger than the number's length, it would cause indexing overflow.
/// Besides, as the same as [`Vec`], slicing results will be `&[u64]` type, which is also immutable.
///
/// ```rust
/// use integer::prelude::*;
///
/// let a = int!([0u64, 1, 2, 3]);
/// let b: u64 = a[0];
/// let c: &[u64] = &a[0..2];  
/// assert_eq!(b, 0);  
/// assert_eq!(c, &[0u64, 1]);
/// ```
///
/// # Calculation
///
/// Integer provides the standard calculations for big numbers, which including add, minus, multiply, divide, modulus,
/// square, power, montgomery exponent modulus, greatest common divisor and bit shifts. Using given functions or overloaded
/// operators and easily complete calculations.
///
/// Operators are also implemented between references and instances, thus could do arithmetic and comparison easilier than functions
/// beacuse useless variables can be automatically consumed.  
///
/// ```rust
/// use integer::prelude::*;
///
/// let ref a = int!(3);
/// let ref b = int!(4);
/// assert_eq!(a + b, a.add_with(b));
///
/// let c = int!(36);
/// assert!((a ^ 2) * b == c);
/// ```
///
/// # Display
///
/// The Integer implements [`Display`] trait, which prints out the decimal value string. On the other hand, [`hex`] function and
/// [`decimal`] function provide value strings for further use.
///
/// ```rust
/// use integer::prelude::*;
///
/// let a = int!([255u64, 1]);
/// println!("{}", a);
/// println!("{}", a.decimal());
/// println!("{}", a.hex());
/// ```
///
/// # Warning and Panics
///
/// Because of some bugs in optimization of rust code with heavy llvm inline assembly code, some unexpected errors will occur if
/// you use the version of native target cpu in release, which probably come from the optimization of volatile variables
/// and registers. However, whereas the version of unoptimized works fine, the version of native target cpu in debug is a good alternative
/// for using native target cpu's features. If you just use the general x86_64 release version, the speed is slight faster than the
/// native target cpu version if the bit length is not long enough.
///
///
/// [`try_convert`]: #method.try_convert
/// [`random_prime`]: #method.random_prime
/// [`Display`]: https://doc.rust-lang.org/nightly/std/fmt/trait.Display.html
/// [`hex`]: #method.hex
/// [`decimal`]: #method.decimal
pub struct Integer {
	sign: i8,
	/*bit length*/
	bitlen: usize,
	/*bytes been used to store */
	len: usize,
	/* alloc size */
	size: usize,
	/* concatenate position */
	hook: usize,
	/* data */
	data: Vec<u64>,
}

/// a divide result type which represents the quotient and the remiander
pub struct DivideResult(pub Integer, pub Integer);

impl Clone for Integer {
	fn clone(&self) -> Self {
		Integer {
			sign: self.sign,
			bitlen: self.bitlen,
			len: self.len,
			size: self.size,
			hook: self.hook,
			data: self.data.clone(),
		}
	}

	fn clone_from(&mut self, source: &Self) {
		self.sign = source.sign;
		self.bitlen = source.bitlen;
		self.len = source.len;
		self.size = source.size;
		self.hook = source.hook;
		self.data.clone_from(&source.data);
	}
}

impl Integer {
	/// Constructs a new Integer zero.
	///
	/// The Integer has specific capacity of bit size. Because of the available
	/// and correctness of other attributes, it will have at least one block length
	/// and ceiling bit size.
	///
	/// # Panics
	///
	/// If *len* equals zero.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let mut zero: Integer = Integer::new(64);
	/// ```
	pub fn new(len: usize) -> Self {
		assert!(len > 0, "The bit length must be positive.");
		let vec_size = (len + BLOCK_BIT - 1) / BLOCK_BIT;
		Integer {
			sign: 0,
			bitlen: 0,
			len: 1,
			size: vec_size,
			hook: 0,
			data: vec![0u64; vec_size],
		}
	}

	/// Constructs a new Integer by value string.
	///
	/// The value string should be hexed so that the number can convert correctly.
	/// If the string does not have the operator, it promises that it is positive.
	///
	/// # Panics
	///
	/// *digits* is empty or invalid.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let num = Integer::from("123456789abcdef");
	/// ```
	pub fn from(digits: &str) -> Self {
		assert!(digits.len() > 0, "Invalid string length.");
		let (offset, sgn) = match digits.get(0..=0) {
			Some("-") => (1, -1),
			Some("+") => (1, 1),
			_ => (0, 1),
		};
		let block_size = BLOCK_SIZE * 2;
		let vec_size = (digits.len() - offset + block_size - 1) / block_size;
		let mut vdata = vec![0u64; vec_size];
		let (mut l, mut r) = (digits.len(), 0);
		for idx in 0..vec_size {
			match vec_size - idx {
				1 => {
					r = l - 1;
					l = offset;
				}
				_ => {
					r = l - 1;
					l = l - block_size;
				}
			};
			if let Some(u_str) = digits.get(l..=r) {
				match u64::from_str_radix(u_str, 16) {
					Ok(n) => vdata[idx] = n,
					Err(e) => panic!("{}, digits: {}", e, digits),
				}
			}
		}
		let mut res = Integer {
			sign: sgn,
			bitlen: vec_size * BLOCK_BIT,
			len: vec_size,
			size: vec_size,
			hook: 0,
			data: vdata,
		};
		res.regularize();
		res
	}

	/// Construct a new Integer from other types.
	///
	/// The result Integer instance copies value from given type's memory address
	/// and read bytes with in type's size, which means it should be implemented `Sized` and `Clone`.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let mask = Integer::try_convert(-1i128, 1);
	/// ```
	pub fn try_convert<T: Clone>(num: T, sign: isize) -> Self {
		<T as Convert>::try_convert(num, sign)
	}

	/// Returns the value in the i-th bit.
	///
	/// # Panics
	///
	/// Index overflow if *i* is greater or equal the bit length.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let a = int!(7);
	/// let b: u8 = a.at(2);
	/// assert_eq!(b, 1);
	/// ```
	pub fn at(&self, i: usize) -> u8 {
		assert!(i < self.bitlen, "Index overflow, {} in {}.", i, self.bitlen);
		((self.data[i / BLOCK_BIT] >> (i % BLOCK_BIT)) & 1) as u8
	}

	/// Returns a slice copy of the original Integer.
	///
	/// The copy operations are bit based, Edges are inclusive.
	///
	/// # Panics
	/// Index overflow if *l* is no less than *r*
	/// or *r* is no less than bit length.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let a = int!([0u64, 1, 1, 3]);
	/// let b = int!([1u64, 1]);
	/// assert_eq!(a.slice(64, 191), b);
	/// ```
	pub fn slice(&self, l: usize, r: usize) -> Integer {
		assert!(
			l <= r && r <= self.bitlen,
			"Index overflow, {}-{} in {}.",
			l,
			r,
			self.bitlen
		);
		let vec_size = (r - l + BLOCK_BIT) / BLOCK_BIT;
		let (lpad, rpad) = (l % BLOCK_BIT, BLOCK_BIT - r % BLOCK_BIT - 1);
		let slice = &self.data[(l / BLOCK_BIT)..=(r / BLOCK_BIT)];
		let mut raw = vec![0u64; slice.len()];
		raw.copy_from_slice(slice);
		if lpad > 0 {
			shr(&mut raw, lpad);
		}
		raw[vec_size - 1] &= BLOCK_MAX >> (lpad + rpad);
		raw.truncate(vec_size);
		let mut res = Integer {
			sign: self.sign,
			bitlen: vec_size * BLOCK_BIT,
			len: vec_size,
			size: vec_size,
			hook: 0,
			data: raw,
		};
		res.regularize();
		res
	}

	/// Shift bits towards left.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let a = int!(1);
	/// let b = int!(2);
	/// assert_eq!(a.shift_left(1), b);
	/// ```
	pub fn shift_left(&self, rhs: usize) -> Integer {
		match rhs {
			0 => self.clone(),
			_ => {
				let min_size = (self.bitlen + rhs as usize + BLOCK_BIT - 1) / BLOCK_BIT;
				let mut res = self.clone();
				if res.size < min_size {
					res.resize(min_size);
				}
				res.len = min_size;
				res.fshl(rhs);
				res
			}
		}
	}

	/// Shift bits towards right.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let a = int!(1);
	/// let b = int!(2);
	/// assert_eq!(b.shift_right(1), a);
	/// ```
	pub fn shift_right(&self, rhs: usize) -> Integer {
		match rhs {
			0 => self.clone(),
			_ => {
				let mut res = self.clone();
				res.fshr(rhs);
				res
			}
		}
	}

	/// Returns the negative original value.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let a = int!(1);
	/// let b = int!(1, -1);
	/// assert_eq!(a.negate(), b);
	/// ```
	pub fn negate(&self) -> Integer {
		Integer {
			sign: -self.sign,
			bitlen: self.bitlen,
			len: self.len,
			size: self.size,
			hook: self.hook,
			data: self.data.clone(),
		}
	}

	/// Adds another Integer.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let ref a = int!(1);
	/// let ref b = int!(2);
	/// assert_eq!(a.add_with(a), b);
	/// assert_eq!(a + a, b);
	/// ```
	pub fn add_with(&self, rhs: &Integer) -> Integer {
		match (self.sign, rhs.sign) {
			(_, 0) => self.clone(),
			(0, _) => rhs.clone(),
			(l, r) if l != r => self.subtract_with(&rhs.negate()),
			(l, _) => {
				let vec_size = max!(self.len, rhs.len) + 1;
				let mut res = Integer {
					sign: l,
					bitlen: 0,
					len: vec_size,
					size: vec_size,
					hook: 0,
					data: vec![0u64; vec_size],
				};
				if self.len > rhs.len {
					addcarry(&mut res.data, &self.data[..self.len], &rhs.data[..rhs.len]);
				} else {
					addcarry(&mut res.data, &rhs.data[..rhs.len], &self.data[..self.len]);
				}
				res.regularize();
				res
			}
		}
	}

	/// Subtracts another Integer.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let ref a = int!(1);
	/// let ref b = int!(2);
	/// assert_eq!(b.subtract_with(a), a);
	/// assert_eq!(b - a, a);
	/// ```
	pub fn subtract_with(&self, rhs: &Integer) -> Integer {
		match (self.sign, rhs.sign) {
			(_, 0) => self.clone(),
			(0, _) => rhs.negate(),
			(l, r) if l != r => self.add_with(&rhs.negate()),
			(l, _) => match (self.compare(rhs), l) {
				(Ordering::Equal, _) => Integer::zero(),
				(cmp, sgn) if cmp as i8 != sgn => rhs.subtract_with(self).negate(),
				(_, sgn) => {
					let vec_size = max!(self.len, rhs.len);
					let mut res = Integer {
						sign: sgn,
						bitlen: 0,
						len: vec_size,
						size: vec_size,
						hook: 0,
						data: vec![0u64; vec_size],
					};
					subborrow(&mut res.data, &self.data[..self.len], &rhs.data[..rhs.len]);
					res.regularize();
					res
				}
			},
		}
	}

	/// Multiplies another Integer.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let ref a = int!(1);
	/// let ref b = int!(2);
	/// assert_eq!(a.multiply_with(b), b);
	/// assert_eq!(a * b, b);
	/// ```
	pub fn multiply_with(&self, rhs: &Integer) -> Integer {
		if self.sign == 0 && rhs.sign == 0 {
			Integer::zero()
		} else {
			let (lx, ly) = (self.len, rhs.len);
			if lx < MUL_BLOCK_THRESHOLD || ly < MUL_BLOCK_THRESHOLD {
				self.direct_multiply(rhs)
			} else if lx < MUL_THRESHOLD || ly < MUL_THRESHOLD {
				self.karatsuba(rhs)
			} else {
				self.toom_cook(rhs)
			}
		}
	}

	/// Divides another Integer.
	///
	/// The return type is [`DivideResult`], which combines quotient and remainder.
	/// The remainder is always greater than zero because of montgomery division.
	/// If the dividend is negative, the quotient multiplies the divisor then adds the
	/// remiander is not equal to the dividend.
	///
	/// # Panics
	///
	/// *rhs* is negative.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let ref a = int!(1);
	/// let ref b = int!(2);
	/// let DivideResult(quo, rem) = b.divide_with(a);
	/// assert_eq!(b / a, quo);
	/// assert_eq!(b % a, rem);
	/// ```
	///
	/// [`DivideResult`]: struct.DivideResult.html
	pub fn divide_with(&self, rhs: &Integer) -> DivideResult {
		assert!(rhs.sign > 0, "Negative divisor.");
		let DivideResult(quotient, remainder) =
			match unsigned_compare(&self.data[..self.len], &rhs.data[..rhs.len]) {
				0 => DivideResult(
					Integer::try_convert(1u64, self.sign as isize),
					Integer::zero(),
				),
				-1 => DivideResult(Integer::zero(), self.clone()),
				_ => {
					let trail = rhs.num_of_trailing_zero() as usize;
					let (divd, dec) = match trail > 0 {
						true => (self.shift_right(trail).abs(), rhs.shift_right(trail)),
						false => (self.abs(), rhs.clone()),
					};
					let DivideResult(mut quo, mut rem) = match (divd.len, dec.len) {
						(ldivd, 1) => {
							/* long division */
							let mut quo = Integer {
								sign: self.sign,
								bitlen: 0,
								len: ldivd,
								size: ldivd,
								hook: 0,
								data: vec![0u64; ldivd],
							};
							let rem = divide_block(&mut quo.data, &divd.data[..ldivd], dec.data[0]);
							quo.regularize();
							DivideResult(quo, Integer::try_convert(rem, self.sign as isize))
						}
						(ldivd, ldec) if ldec < DIV_THRESHOLD || (ldivd - ldec) < DIV_OFFSET => {
							divd.divknuth(&dec)
						}
						_ => divd.burnikelziegler(&dec),
					};
					quo.sign *= self.sign;
					rem.sign *= self.sign;
					if trail > 0 {
						rem = rem.shift_left(trail).add_with(&self.slice(0, trail - 1));
					}
					DivideResult(quo, rem)
				}
			};
		if remainder.sign < 0 {
			DivideResult(quotient, remainder.add_with(rhs))
		} else {
			DivideResult(quotient, remainder)
		}
	}

	/// Returns the power of the Integer.
	///
	/// The exponent is an `u32` number not a Integer.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let ref a = int!(2);
	/// let ref b = int!(8);
	/// assert_eq!(a.power(3), b);
	/// assert_eq!(a ^ 3, b);
	/// ```
	pub fn power(&self, exp: u32) -> Integer {
		if self.sign == 0 {
			return Integer::zero();
		}

		let trail = self.num_of_trailing_zero() as usize;
		let exptrail = trail * exp as usize;

		/* when x is the power of two */
		if trail + 1 == self.bitlen {
			let vec_size = exptrail / BLOCK_BIT + 1;
			let mut res = Integer {
				sign: self.sign,
				bitlen: exptrail + 1,
				len: vec_size,
				size: vec_size,
				hook: 0,
				data: vec![0u64; vec_size],
			};
			if exp % 2 == 0 {
				res.sign = 1;
			}
			res.data[vec_size - 1] = 1 << (exptrail as u64 % BLOCK_BIT as u64);
			return res;
		}

		/* get the remaining part to calculate */
		let remains = self.shift_right(trail);
		let mut rexp = exp;
		let mut head = match (self.bitlen - trail) * exp as usize <= 128 {
			true => {
				let (mut head, mut base) = (1u128, remains.data[0] as u128);
				while rexp > 0 {
					if (rexp & 1) == 1 {
						head *= base;
					}
					rexp >>= 1;
					if rexp > 0 {
						base *= base;
					}
				}
				Integer::try_convert(head, 1)
			}
			false => {
				let (mut head, mut base) = (Integer::one(), remains);
				while rexp > 0 {
					if (rexp & 1) == 1 {
						head = head.multiply_with(&base);
					}
					rexp >>= 1;
					if rexp > 0 {
						base = base.square();
					}
				}
				head
			}
		};
		if exptrail > 0 {
			head = head.shift_left(exptrail);
		}
		head
	}

	/// Returns the square of the Integer.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let ref a = int!(2);
	/// let ref b = int!(4);
	/// assert_eq!(a.square(), b);
	/// assert_eq!(a ^ 2, b);
	/// ```
	pub fn square(&self) -> Integer {
		if self.sign == 0 {
			Integer::zero()
		} else {
			match self.len {
				0..=MUL_BLOCK_THRESHOLD => self.direct_multiply(self),
				MUL_BLOCK_THRESHOLD..=MUL_THRESHOLD => self.squarekaratsuba(),
				_ => self.toom_cook(self),
			}
		}
	}

	/// Returns the greatest common divisor of two Integers.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let ref a = int!(2);
	/// let ref b = int!(4);
	/// assert_eq!(a.gcd(b), a);
	/// ```
	pub fn gcd(&self, rhs: &Integer) -> Integer {
		self.gcdivisor(rhs)
	}

	/// Returns the montgomery exponent modulus of the Integer.
	///
	/// The remainder is always greater than zero. The negative exponent is acceptable.
	///
	/// # Panics
	///
	/// *modulus* is negative.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let ref a = int!(3);
	/// let ref b = int!(4);
	/// let ref c = int!(5);
	/// assert_eq!(a.powmod(c, b), a);
	/// ```
	pub fn powmod(&self, exp: &Integer, modulus: &Integer) -> Integer {
		self.expmod(exp, modulus)
	}

	/// Returns the absolute value of the Integer.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let ref a = int!(1, -1);
	/// let ref b = int!(1);
	/// assert_eq!(a.abs(), b);
	/// assert_eq!(b.abs(), b);
	/// ```
	pub fn abs(&self) -> Integer {
		Integer {
			sign: self.sign.abs(),
			bitlen: self.bitlen,
			len: self.len,
			size: self.size,
			hook: 0,
			data: self.data.clone(),
		}
	}

	/// Compares two Integers with signs.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// use std::cmp::Ordering;
	///
	/// let ref a = int!(1);
	/// let ref b = int!(2);
	/// assert_eq!(a.compare(b), Ordering::Less);
	/// assert!(a < b);
	/// ```
	pub fn compare(&self, rhs: &Integer) -> Ordering {
		let sgn = match (self.sign, rhs.sign) {
			(l, r) if l != r => l - r,
			(l, r) if l == 0 && r == 0 => 0,
			_ => self.ucompare(rhs) * self.sign,
		};
		if sgn > 0 {
			Ordering::Greater
		} else if sgn == 0 {
			Ordering::Equal
		} else {
			Ordering::Less
		}
	}

	/// Returns the value string in decimal
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let a = int!(100);
	/// println!("{}", a.decimal());
	/// ```
	pub fn decimal(&self) -> String {
		if self.sign == 0 {
			return String::from("0");
		}
		let (mut str_data, mut val) = (Vec::new(), self.abs());
		let mask = Integer::try_convert(10000000000000000000u64, 1); // 10 ** 19
		while val.bitlen > 64 {
			let DivideResult(quo, rem) = val.divide_with(&mask);
			str_data.push(format!("{:020?}", rem.data[0]));
			val = quo;
		}
		str_data.push(format!("{}", val.data[0]));
		if self.sign < 0 {
			str_data.push(String::from("-"));
		}
		str_data.reverse();
		str_data.concat()
	}

	/// Returns the value string in hex
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let a = int!(100);
	/// println!("{}", a.hex());
	/// ```
	pub fn hex(&self) -> String {
		if self.sign == 0 {
			return String::from("0");
		}
		let mut str_data: Vec<String> = self.data[..self.len]
			.iter()
			.map(|n| format!("{:016x?}", n))
			.rev()
			.collect();
		if self.sign < 0 {
			str_data.insert(0, String::from("-"));
		}
		str_data.concat()
	}

	/// Checks the Integer is prime or not in given precision(1..100).
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let a = int!(3);
	/// assert!(a.is_prime(100));
	/// ```
	pub fn is_prime(&self, precision: i32) -> bool {
		let n = (precision + 1) / 2;
		// The relationship between the certainty and the number of rounds
		// we perform is given in the draft standard ANSI X9.80, "PRIME
		// NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES".
		if self.bitlen < 100 {
			let rounds = min!(n, 50);
			self.passes_miller_rabin(rounds)
		} else {
			let mut rounds = match self.bitlen {
				100..=255 => 27,
				256..=511 => 15,
				512..=767 => 8,
				768..=1023 => 4,
				_ => 2,
			};
			rounds = min!(n, rounds);
			self.passes_miller_rabin(rounds) && self.passes_lucas_lehmer()
		}
	}

	/// Rewind the hook
	///
	/// ***This is useless for this version***
	#[cold]
	#[inline]
	pub fn rewind(&mut self) -> bool {
		if self.hook == 0 {
			false
		} else {
			self.hook = 0;
			true
		}
	}

	/// Checks the Integer is zero or not
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let a = Integer::zero();
	/// assert!(a.is_zero());
	/// ```
	#[inline]
	pub fn is_zero(&self) -> bool {
		self.sign == 0
	}

	/// Checks the Integer is odd or not
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let a = Integer::one();
	/// assert!(a.is_odd());
	/// ```
	#[inline]
	pub fn is_odd(&self) -> bool {
		self.data[0] & 1 == 1
	}

	/// Returns the bit length of the Integer
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let a = int!(8);
	/// assert_eq!(a.bits(), 4);
	/// ```
	#[inline]
	pub fn bits(&self) -> u32 {
		self.bitlen as u32
	}

	/// Returns how many blocks in the Integer
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let a = int!(-1i128);
	/// assert_eq!(a.nblocks(), 2);
	/// ```
	#[inline]
	pub fn nblocks(&self) -> u32 {
		self.len as u32
	}

	/// Returns how many blocks allocated in the Integer
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let a = int!(1i128);
	/// assert_eq!(a.alloc_size(), 2);
	/// ```
	#[inline]
	pub fn alloc_size(&self) -> u32 {
		self.size as u32
	}

	/// Returns a raw pointer to the Integer's blocks
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let a = int!(1i128);
	/// let b = a.as_raw_ptr();
	/// unsafe { assert_eq!(1, b.read()); }
	/// ```
	#[inline]
	pub fn as_raw_ptr(&self) -> *const u64 {
		let ptr = self.data.as_ptr();
		ptr
	}

	/// Construct a random Integer in given bit length
	///
	/// # Panics
	///
	/// *bits* equals zero.
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let a = Integer::random(2048);
	/// ```
	#[inline]
	pub fn random(bits: u32) -> Integer {
		assert!(bits > 0, "Length should not be zero.");
		let vec_size = (bits as usize + BLOCK_BIT - 1) / BLOCK_BIT;
		let mut vec_data = vec![0u64; vec_size];
		let mut rng = rand::rngs::StdRng::from_entropy();
		for i in 0..vec_size - 1 {
			vec_data[i] = random_u64(&mut rng, BLOCK_BIT as u32);
		}
		vec_data[vec_size - 1] = match bits % BLOCK_BIT as u32 {
			0 => (1 << (BLOCK_BIT - 1)) | random_u64(&mut rng, BLOCK_BIT as u32 - 1),
			1 => 1,
			n => (1 << (n - 1)) | random_u64(&mut rng, n - 1),
		};
		Integer {
			sign: 1,
			bitlen: bits as usize,
			len: vec_size,
			size: vec_size,
			hook: 0,
			data: vec_data,
		}
	}

	/// Construct a random prime Integer in given bit length
	///
	/// # Examples
	///
	/// ```rust
	/// use integer::prelude::*;
	///
	/// let a = Integer::random_prime(2048, 100);
	/// ```
	#[inline]
	pub fn random_prime(bits: u32, precision: i32) -> Integer {
		/// war range
		let mut number = Self::random(bits);
		let prime_prod = Integer::try_convert(PRIME_PRODUCT, 1);

		/* make it odd */
		if number.data[0] & 1 == 0 {
			number.data[0] += 1;
		}
		loop {
			assert!(number.bitlen == bits as usize);

			if bits < PRIME_PROBE_THRESHOLD {
				/* small prime pre-test */
				if bits > 6 {
					let rem = number.divide_with(&prime_prod).1.data[0];
					if SMALL_PRIMES.iter().any(|&x| rem % x == 0) {
						number = number.add_with(&Integer::two());
						continue; // candidate is composite; try another
					}
				}

				/* all candidates of bitLength 2 and 3 are prime by this point */
				if bits < 4 {
					return number;
				}

				/* The expensive test */
				if number.is_prime(precision) {
					return number;
				}

				number = number.add_with(&Integer::two());
			} else {
				/* Start at previous even number */
				if number.data[0] & 1 == 1 {
					number.data[0] -= 1;
				}

				let searchlen = Sieve::invert_length(bits as usize);
				let step = Integer::try_convert(2 * searchlen, 1);
				let small_sieve = Sieve::small_sieve();
				loop {
					let sieve = Sieve::sieve(&number.data[..number.len], searchlen, &small_sieve);
					if let Some(candidate) = number.sieve_retrieve(sieve, precision) {
						return candidate;
					}
					number = number.add_with(&step);
				}
			}
		}
	}

	/// Constructs an Integer and its value is zero.
	pub fn zero() -> Integer {
		Integer {
			sign: 0,
			bitlen: 0,
			len: 1,
			size: 1,
			hook: 0,
			data: vec![0u64; 1],
		}
	}

	/// Constructs an Integer and its value is one.
	pub fn one() -> Integer {
		Integer {
			sign: 1,
			bitlen: 1,
			len: 1,
			size: 1,
			hook: 0,
			data: vec![1u64; 1],
		}
	}

	/// Constructs an Integer and its value is two.
	pub fn two() -> Integer {
		Integer {
			sign: 1,
			bitlen: 2,
			len: 1,
			size: 1,
			hook: 0,
			data: vec![2u64; 1],
		}
	}

	/// Constructs an Integer and its value is three.
	pub fn three() -> Integer {
		Integer {
			sign: 1,
			bitlen: 2,
			len: 1,
			size: 1,
			hook: 0,
			data: vec![3u64; 1],
		}
	}

	fn regularize(&mut self) {
		let leading = self.num_of_leading_zero();
		self.bitlen = self.len * BLOCK_BIT - leading as usize;
		if self.bitlen == 0 {
			self.sign = 0;
			self.len = 1;
		} else {
			self.len = (self.bitlen + BLOCK_BIT - 1) / BLOCK_BIT;
		}
	}

	fn resize(&mut self, newsize: usize) -> bool {
		self.data.resize(newsize, 0u64);
		self.size = self.data.len();
		self.size == newsize
	}

	fn ucompare(&self, rhs: &Integer) -> i8 {
		unsigned_compare(&self.data[..self.len], &rhs.data[..rhs.len])
	}

	fn num_of_trailing_zero(&self) -> usize {
		trailing_zero(&self.data[..self.len]) as usize
	}

	fn num_of_leading_zero(&self) -> usize {
		leading_zero(&self.data[..self.len]) as usize
	}

	fn get_upper(&self, offblk: usize) -> Integer {
		match offblk < self.len {
			true => {
				let mut res = Integer {
					sign: self.sign,
					bitlen: 0,
					len: self.len - offblk,
					size: self.len - offblk,
					hook: 0,
					data: vec![0u64; self.len - offblk],
				};
				res.data.copy_from_slice(&self.data[offblk..self.len]);
				res.regularize();
				res
			}
			false => Integer::zero(),
		}
	}

	fn get_lower(&self, blk: usize) -> Integer {
		match blk {
			0 => Integer::zero(),
			_ => {
				let blk = min!(blk, self.len);
				let mut res = Integer {
					sign: self.sign,
					bitlen: 0,
					len: blk,
					size: blk,
					hook: 0,
					data: vec![0u64; blk],
				};
				res.data.copy_from_slice(&self.data[..blk]);
				res.regularize();
				res
			}
		}
	}
	fn get_slice(&self, offblk: usize, blk: usize) -> Integer {
		match (offblk, blk) {
			(0, b) => self.get_lower(b),
			(o, 0) => self.get_upper(o),
			(o, _) if self.len <= o => Integer::zero(),
			_ => {
				let blk = min!(blk, self.len - offblk);
				let mut res = Integer {
					sign: self.sign,
					bitlen: 0,
					len: blk,
					size: blk,
					hook: 0,
					data: vec![0u64; blk],
				};
				res.data.copy_from_slice(&self.data[offblk..offblk + blk]);
				res.regularize();
				res
			}
		}
	}

	fn fshl(&mut self, bits: usize) {
		assert!(bits > 0);
		let (blk, b) = (bits / BLOCK_BIT, bits % BLOCK_BIT);
		if blk > 0 {
			self.data.copy_within(..(self.len - blk), blk);
			fill(&mut self.data[..blk], 0u64);
		}
		shl(&mut self.data[..self.len], b);
		self.regularize();
	}
	fn fshr(&mut self, bits: usize) {
		assert!(bits > 0);
		let (blk, b) = (bits / BLOCK_BIT, bits % BLOCK_BIT);
		if blk > 0 {
			self.data.copy_within(blk.., 0);
			fill(&mut self.data[(self.len - blk)..], 0u64);
		}
		shr(&mut self.data[..self.len], b);
		self.regularize();
	}

	fn gcdivisor(&self, rhs: &Integer) -> Integer {
		let (mut a, mut b) = (self.abs(), rhs.abs());
		while b.len != 0 {
			/* if approx. length, calculates the binary GCD */
			if diff(a.len, b.len) < 2 {
				let (mut u, mut v) = (a, b);
				/* B1 the greatest 2^k */
				let (su, sv) = (u.num_of_trailing_zero(), v.num_of_trailing_zero());
				let k = min!(su, sv);
				if k > 0 {
					u.fshr(k);
					v.fshr(k);
				}

				/* B2 initialize */
				let (mut t, mut t_sign) = match su == k {
					true => (v.clone(), -1),
					false => (u.clone(), 1),
				};
				loop {
					let t_trail = t.num_of_trailing_zero();
					/* B3 B4 test t is even and shift */
					if t_trail > 0 {
						t.fshr(t_trail);
					}
					/* B5 reset max(u, v) */
					if t_sign > 0 {
						u = t;
					} else {
						v = t;
					}
					/* for length = 1 case */
					if u.len < 2 && v.len < 2 {
						let (mut p, mut q) = (u.data[0], v.data[0]);
						let (p_trail, q_trail) = (p.trailing_zeros(), q.trailing_zeros());
						p >>= p_trail;
						q >>= q_trail;
						while p != q {
							if p > q {
								p -= q;
								p >>= p.trailing_zeros();
							} else {
								q -= p;
								q >>= q.trailing_zeros();
							}
						}
						p <<= min!(p_trail, q_trail);
						match k > 0 {
							true => return Integer::try_convert(p, 1).shift_left(k),
							false => return Integer::try_convert(p, 1),
						}
					}

					/* B6 t = (u - v), and check t != 0 */
					t_sign = u.compare(&v) as i8;

					match t_sign {
						-1 => t = v.subtract_with(&u),
						0 => break,
						_ => t = u.subtract_with(&v),
					}
				}

				match k > 0 {
					true => return u.shift_left(k),
					false => return u.clone(),
				}
			}

			/* Euclid's algorithm */
			let DivideResult(_, r) = a.divide_with(&b);
			a = b;
			b = r;
		}
		a.clone()
	}

	fn expmod(&self, exp: &Integer, modulus: &Integer) -> Integer {
		assert!(modulus.sign > 0, "Negative modulus");
		if (self.sign == 1 && self.bitlen == 1) || exp.sign == 0 {
			if modulus.bitlen == 1 {
				return Integer::zero();
			} else {
				return Integer::one();
			}
		} else if self.sign == 0 {
			return Integer::zero();
		} else if self.sign < 0 && self.bitlen == 1 && (exp.data[0] & 1) == 0 {
			if modulus.bitlen == 1 {
				return Integer::zero();
			} else {
				return Integer::one();
			}
		}
		/* if exp is negate, negate exp and calculate its inverse. */
		let need_inverse = exp.sign < 0;
		let exp = match need_inverse {
			true => exp.negate(),
			false => exp.clone(),
		};
		let mut base = match self.sign < 0 || self.compare(modulus) >= Ordering::Equal {
			true => self.divide_with(modulus).1,
			false => self.clone(),
		};

		let mut res = match modulus.data[0] & 1 {
			1 => base.oddpowmod(&exp, modulus), /* Odd modulus */
			_ => {
				/* Even modulus */
				/* Tear m apart into odd part (oddm) and power of 2 (pm) */
				let p = modulus.num_of_trailing_zero();
				let oddm = modulus.shift_right(p);
				let pm = Integer::one().shift_left(p);

				/* Calculate new base from oddm */
				let base2 = match self.sign < 0 || self.compare(&oddm) >= Ordering::Equal {
					true => self.divide_with(&oddm).1,
					false => self.clone(),
				};

				/* Caculate (base ** exponent) mod oddm */
				let a1 = match oddm.bitlen == 1 {
					true => Integer::zero(),
					false => base2.oddpowmod(&exp, &oddm),
				};

				/* Calculate (this ** exponent) mod pm */
				/* Perform exponentiation using repeated squaring trick,
				 * chopping off high order bits as indicated by modulus.
				 */
				let mut a2 = Integer::one();
				if p < base.bitlen {
					base = base.slice(0, p - 1);
				}
				let mut rexp = 0;
				let limit = match base.data[0] & 1 {
					1 => min!(p - 1, exp.bitlen),
					_ => exp.bitlen,
				};
				while rexp < limit {
					if exp.at(rexp) == 1 {
						a2 = a2.multiply_with(&base);
						if p < a2.bitlen {
							a2 = a2.slice(0, p - 1);
						}
					}
					rexp += 1;
					if rexp < limit {
						base = base.square();
						if p < base.bitlen {
							base = base.slice(0, p - 1);
						}
					}
				}

				/* Combine results using Chinese Remainder Theorem */
				let y1 = pm.mod_inverse(&oddm); // pm^-1 = y1 (mod oddm)
				let y2 = oddm.mod_inverse(&pm); // oddm^-1 = y2 (mod pm)

				match modulus.len < usize::MAX / 2 {
					true => {
						a1.multiply_with(&pm)
							.multiply_with(&y1)
							.add_with(&a2.multiply_with(&oddm).multiply_with(&y2))
							.divide_with(&modulus)
							.1
					}
					false => panic!("the size of modulus is out of range."),
				}
			}
		};

		if need_inverse {
			res = res.mod_inverse(modulus);
		}
		res
	}

	fn direct_multiply(&self, rhs: &Integer) -> Integer {
		let vec_size = self.len + rhs.len;
		let mut res = Integer {
			sign: self.sign * rhs.sign,
			bitlen: 0,
			len: vec_size,
			size: vec_size,
			hook: 0,
			data: vec![0u64; vec_size],
		};
		multiply(&mut res.data, &self.data[..self.len], &rhs.data[..rhs.len]);
		res.regularize();
		res
	}

	fn karatsuba(&self, rhs: &Integer) -> Integer {
		let half = (max!(self.len, rhs.len) + 1) / 2;
		let (ux, wx) = (self.get_upper(half), self.get_lower(half));
		let (uy, wy) = (rhs.get_upper(half), rhs.get_lower(half));
		let (f, g) = rayon::join(|| ux.multiply_with(&uy), || wx.multiply_with(&wy));
		let h = wx
			.add_with(&ux)
			.multiply_with(&wy.add_with(&uy))
			.subtract_with(&f)
			.subtract_with(&g);
		let mut res = f
			.shift_left(half)
			.add_with(&h)
			.shift_left(half)
			.add_with(&g);
		res.sign = self.sign * rhs.sign;
		res.regularize();
		res
	}

	fn squarekaratsuba(&self) -> Integer {
		let half = (self.len + 1) / 2;
		let (ux, wx) = (self.get_upper(half), self.get_lower(half));
		let (f, g) = rayon::join(|| ux.square(), || wx.square());
		let h = wx.multiply_with(&ux).shift_left(1);
		let mut res = f
			.shift_left(half * BLOCK_BIT)
			.add_with(&h)
			.shift_left(half * BLOCK_BIT)
			.add_with(&g);
		res.sign = self.sign * self.sign;
		res.regularize();
		res
	}

	fn toom_cook(&self, rhs: &Integer) -> Integer {
		let k = (max!(self.len, rhs.len) + 2) / 3;
		/* split x and y into 3 slices and x0 / y0 is the least significant part */
		let (x0, x1, x2) = (
			self.get_lower(k),
			self.get_slice(k, k),
			self.get_upper(2 * k),
		);
		let (y0, y1, y2) = (rhs.get_lower(k), rhs.get_slice(k, k), rhs.get_upper(2 * k));
		/* calculate parts to figure out values */
		let (mut px, mut py) = (x0.add_with(&x2), y0.add_with(&y2));
		let (vinf, v0) = rayon::join(|| x2.multiply_with(&y2), || x0.multiply_with(&y0));
		let vm1 = px.subtract_with(&x1).multiply_with(&py.subtract_with(&y1));
		px = px.add_with(&x1);
		py = py.add_with(&y1);
		let (v1, v2) = rayon::join(
			|| px.multiply_with(&py),
			|| {
				px.add_with(&x2)
					.shift_left(1)
					.subtract_with(&x0)
					.multiply_with(&py.add_with(&y2).shift_left(1).subtract_with(&y0))
			},
		);
		/* calculate parameters */
		let DivideResult(mut r2, _) = v2.subtract_with(&vm1).divide_with(&Integer::three());
		let (mut rm1, mut r1) = rayon::join(
			|| v1.subtract_with(&vm1).shift_right(1),
			|| v1.subtract_with(&v0),
		);
		r2 = r2
			.subtract_with(&r1)
			.shift_right(1)
			.subtract_with(&vinf.shift_left(1));
		r1 = r1.subtract_with(&rm1).subtract_with(&vinf);
		rm1 = rm1.subtract_with(&r2);
		/* shift and combine */
		let kbits = k * BLOCK_BIT;
		let mut res = vinf
			.shift_left(kbits)
			.add_with(&r2)
			.shift_left(kbits)
			.add_with(&r1)
			.shift_left(kbits)
			.add_with(&rm1)
			.shift_left(kbits)
			.add_with(&v0);
		res.sign = self.sign;
		res.regularize();
		res
	}

	fn divknuth(&self, rhs: &Integer) -> DivideResult {
		/* D1 normalize */
		let head = rhs.num_of_leading_zero();
		assert!(head < BLOCK_BIT);
		let mut divisor = rhs.clone();
		let mut value = self.clone();
		value.resize(self.len + 1);
		value.len = self.len + 1;
		if head > 0 {
			divisor.fshl(head);
			value.fshl(head);
		}
		value.len = self.len + 1;
		let (ldiv, lquo) = (divisor.len, value.len - divisor.len + 1);
		let mut quo_data = vec![0_u64; lquo];

		/* D2 initialized j */
		let (dh, dl) = (
			divisor.data[ldiv - 1] as u128,
			divisor.data[ldiv - 2] as u128,
		);
		for j in (0..=lquo - 2).rev() {
			/* D3 calculate qhi */
			let (vh, vm) = (
				value.data[j + ldiv] as u128,
				value.data[j + ldiv - 1] as u128,
			);
			let mut v = (vh << BLOCK_BIT) + vm;
			let (mut qhi, mut vr) = (v / dh, v % dh);
			if qhi == 0 && j > 0 {
				continue;
			}
			let vl = value.data[j + ldiv - 2] as u128;
			v = (vr << BLOCK_BIT) + vl;
			if qhi == BLOCK_BIAS || (qhi != 0 && (dl * qhi) > v) {
				qhi -= 1;
				vr += dh;
				v = (vr << BLOCK_BIT) + vl;
				if vr < BLOCK_BIAS && (qhi == BLOCK_BIAS || (dl * qhi) > v) {
					qhi -= 1;
				}
			}
			/* D4 multiply and subtract */
			let (qd, vj) = (
				divisor.multiply_with(&Integer::try_convert(qhi, 1)),
				value.get_slice(j, ldiv + 1),
			);
			let mut v_new = vj.subtract_with(&qd);
			/* D5 test remainder */
			if v_new.sign < 0 {
				/* D6 add back */
				qhi -= 1;
				v_new = v_new.add_with(&divisor);
			}
			v_new.resize(ldiv + 1);
			let slice: &mut [u64] = &mut value.data[j..(j + ldiv + 1)];
			slice.copy_from_slice(&v_new.data);
			quo_data[j] = qhi as u64;
		} /* D7 loop on j */

		/* D8 unnormalize */
		if head > 0 {
			value.fshr(head);
		}
		let rem = value.get_lower(ldiv);
		let mut quotient = Integer {
			sign: self.sign,
			bitlen: 0,
			len: lquo,
			size: lquo,
			hook: 0,
			data: quo_data,
		};
		quotient.regularize();
		DivideResult(quotient, rem)
	}

	fn burnikelziegler(&self, rhs: &Integer) -> DivideResult {
		/* 1. set m = min{ 2^k | (2^k)*DIVTHRESHOLD > s } */
		let m = 1u64 << (64 - ((rhs.len / DIV_THRESHOLD) as u64).leading_zeros());
		/* 2. j = [s/m], n = j*m */
		let j = (rhs.len as u64 + m - 1) / m;
		let n = (j * m) as usize;
		/* 3. sigma = max{T | (2^T)*B < beta^n} */
		let sigma = max!(0, n * BLOCK_BIT - rhs.len * BLOCK_BIT);
		/* 4.a. set B = B*2^sigma to normalize B */
		let b = rhs.shift_left(sigma);
		/* 4.b. shift A as the same amount */
		let a = self.shift_left(sigma);
		/* 5. set t = min{l >= 2 | A < (beta^(l*n)) / 2} */
		/* t is the number of blocks needed to accommodate A plus one additional bit */
		let t = max!(2, (self.len + (sigma / BLOCK_BIT) + n) / n); // (lx + ((sigma + 1) / DWORDBIT)) / n;
														   /* 6. split A conceptually into t blocks [A(t-1)...A(0)] = A. */
		/* note that the leftmost bit of A(t-1) is 0 by our choice of t */
		/* 7. set Z(t-2) = [A(t-1), A(t-2)] */
		let lz = 2 * n;
		let mut z = a.get_slice((t - 2) * n, (3 - t) * n + self.len - rhs.len);
		if z.size < lz {
			z.resize(lz);
		}
		z.len = lz;
		/* 8. loop on i, using algorithm Divide2n1n divide Z with B */
		let lquo = (t - 1) * n;
		let mut quo_data = vec![0u64; lquo];
		let mut remainder = Integer::zero();
		for i in (0..=t - 2).rev() {
			/* 8.a.	divide Z with B to compute q(i), r(i) such that z(i) = Bq(i) + r(i) */
			let DivideResult(quo, rem) = Integer::divide2n1n(&z, &b);
			/* 8.b. if i > 0, set Z(i-1) = [r(i), A(i-1)] */
			if i > 0 {
				(&mut z.data[..n]).copy_from_slice(&a.data[(i - 1) * n..i * n]);
				(&mut z.data[n..2 * n]).copy_from_slice(&rem.data[..n]);
			}
			remainder = rem;
			(&mut quo_data[i * n..(i + 1) * n]).copy_from_slice(&quo.data[..n]);
		}
		/* 9. shift back the remainder and return the quotient */
		if sigma > 0 {
			remainder.fshr(sigma);
		}
		remainder = remainder.get_lower(rhs.len);
		let mut quotient = Integer {
			sign: self.sign,
			bitlen: 0,
			len: lquo,
			size: lquo,
			hook: 0,
			data: quo_data,
		};
		quotient.regularize();
		DivideResult(quotient, remainder)
	}

	fn divide2n1n(x: &Integer, y: &Integer) -> DivideResult {
		assert_eq!(x.len, 2 * y.len);
		/* 1. n must be bigger than threshold and must be an even-number */
		if y.len < DIV_THRESHOLD || (y.len % 2 != 0) {
			let DivideResult(mut quo, mut rem) = x.divknuth(y);
			quo.len = y.len;
			rem.len = y.len;
			return DivideResult(quo, rem);
		}
		/* 2. split A into four parts with size of 2/n for each,
			* split B into two parts equally.
			* 3. compute high part Q(1) as Q(1) = [A(1)A(2)A(3)]/[B(1)B(2)],
			* remainder R as [R(1,1)R(1,2)]
			*/
		let mut ux = x.get_upper(y.len / 2);
		ux.len = x.len - y.len / 2;
		let DivideResult(q1, rem) = Integer::divide3n2n(&ux, y);
		/* 4. compute low part Q(2) as Q(2) = [R(1,1)R(1,2)A(4)]/[B(1)B(2)], with
			* remainder R */
		let mut lox = x.get_lower(3 * y.len / 2);
		lox.len = x.len - y.len / 2;
		(&mut lox.data[(y.len / 2)..]).copy_from_slice(&rem.data[..y.len]);
		let DivideResult(q2, remainder) = Integer::divide3n2n(&lox, y);
		/* 5. return quotient = [Q(1)Q(2)] and R */
		let mut quo_data = vec![0u64; y.len];
		(&mut quo_data[..(y.len / 2)]).copy_from_slice(&q2.data[..(y.len / 2)]);
		(&mut quo_data[(y.len / 2)..y.len]).copy_from_slice(&q1.data[..(y.len / 2)]);
		let quotient = Integer {
			sign: x.sign,
			bitlen: y.len * BLOCK_BIT,
			len: y.len,
			size: y.len,
			hook: 0,
			data: quo_data,
		};
		DivideResult(quotient, remainder)
	}

	fn divide3n2n(x: &Integer, y: &Integer) -> DivideResult {
		assert_eq!(x.len * 2, y.len * 3);
		let n = y.len / 2;
		let abs_x = x.abs();
		/* 1. split A into three parts as A = [A(1)A(2)A(3)] */
		/* 2. split B into three parts as B = [B(1)B(2)] */
		/* 3. distinguish the cases A(1) < B(1) or A(1) >= B(1) */
		let (mut b1, mut b2, mut a1a2) = (y.get_upper(n), y.get_lower(n), abs_x.get_upper(n));
		b1.len = n;
		b2.len = n;
		a1a2.len = 2 * n;
		let a1 = abs_x.get_upper(2 * n);
		let (r1, mut qhat, d) = match a1.ucompare(&b1) < 0 {
			true => {
				/* 3.a. compute qhat = [A(1)A(2)]/B(1) with remainder R(1) */
				/* 4. compute D = qhat*B(2) */
				let DivideResult(quo, rem) = Integer::divide2n1n(&a1a2, &b1);
				let d = quo.karatsuba(&b2);
				(rem, quo, d)
			}
			false => {
				/* 3.b. set qhat = (beta^n) - 1 and set R(1) = [A(1),A(2)] - [B(1),0UL] + [0UL,B(1)] */
				let qhat_data = vec![BLOCK_MAX; n];
				let qhat = Integer {
					sign: abs_x.sign,
					bitlen: n * BLOCK_BIT,
					len: n,
					size: n,
					hook: 0,
					data: qhat_data,
				};
				let r1 = a1a2
					.subtract_with(&b1.shift_left(n * BLOCK_BIT))
					.add_with(&b1)
					.get_lower(n);
				/* 4. compute D = qhat*B(2) */
				/* in this case, it equals B(2) << n - B(2) */
				let d = b2.shift_left(n * BLOCK_BIT).subtract_with(&b2);
				(r1, qhat, d)
			}
		};
		/* 5. compute Rhat = R(1)*{beta}^n + A(3) - D */
		let a3 = abs_x.get_lower(n);
		let mut rhat = r1.shift_left(n * BLOCK_BIT).add_with(&a3);
		/* 6. as long as rhat < d, rhat adds B from the quotient */
		while rhat.ucompare(&d) < 0 {
			rhat = rhat.add_with(&y);
			qhat = qhat.subtract_with(&Integer::one());
		}
		/* 7. return the remainder and the quotient */
		rhat = rhat.subtract_with(&d);
		rhat.resize(2 * n);
		rhat.sign = x.sign;
		rhat.len = 2 * n;
		qhat.resize(n);
		qhat.sign = x.sign;
		qhat.len = n;
		DivideResult(qhat, rhat)
	}

	/*
	 * The algorithm is adapted from Colin Plumb's C library.
	 *
	 * The window algorithm:
	 * The idea is to keep a running product of b1 = n^(high-order bits of exp)
	 * and then keep appending exponent bits to it.  The following patterns
	 * apply to a 3-bit window (k = 3):
	 * To append   0: square
	 * To append   1: square, multiply by n^1
	 * To append  10: square, multiply by n^1, square
	 * To append  11: square, square, multiply by n^3
	 * To append 100: square, multiply by n^1, square, square
	 * To append 101: square, square, square, multiply by n^5
	 * To append 110: square, square, multiply by n^3, square
	 * To append 111: square, square, square, multiply by n^7
	 *
	 * Since each pattern involves only one multiply, the longer the pattern
	 * the better, except that a 0 (no multiplies) can be appended directly.
	 * We precompute a table of odd powers of n, up to 2^k, and can then
	 * multiply k bits of exponent at a time.  Actually, assuming random
	 * exponents, there is on average one zero bit between needs to
	 * multiply (1/2 of the time there's none, 1/4 of the time there's 1,
	 * 1/8 of the time, there's 2, 1/32 of the time, there's 3, etc.), so
	 * you have to do one multiply per k+1 bits of exponent.
	 *
	 * The loop walks down the exponent, squaring the result buffer as
	 * it goes.  There is a wbits+1 bit lookahead buffer, buf, that is
	 * filled with the upcoming exponent bits.  (What is read after the
	 * end of the exponent is unimportant, but it is filled with zero here.)
	 * When the most-significant bit of this buffer becomes set, i.e.
	 * (buf & tblmask) != 0, we have to decide what pattern to multiply
	 * by, and when to do it.  We decide, remember to do it in future
	 * after a suitable number of squarings have passed (e.g. a pattern
	 * of "100" in the buffer requires that we multiply by n^1 immediately;
	 * a pattern of "110" calls for multiplying by n^3 after one more
	 * squaring), clear the buffer, and continue.
	 *
	 * When we start, there is one more optimization: the result buffer
	 * is implcitly one, so squaring it or multiplying by it can be
	 * optimized away.  Further, if we start with a pattern like "100"
	 * in the lookahead window, rather than placing n into the buffer
	 * and then starting to square it, we have already computed n^2
	 * to compute the odd-powers table, so we can place that into
	 * the buffer and save a squaring.
	 *
	 * This means that if you have a k-bit window, to compute n^z,
	 * where z is the high k bits of the exponent, 1/2 of the time
	 * it requires no squarings.  1/4 of the time, it requires 1
	 * squaring, ... 1/2^(k-1) of the time, it reqires k-2 squarings.
	 * And the remaining 1/2^(k-1) of the time, the top k bits are a
	 * 1 followed by k-1 0 bits, so it again only requires k-2
	 * squarings, not k-1.  The average of these is 1.  Add that
	 * to the one squaring we have to do to compute the table,
	 * and you'll see that a k-bit window saves k-2 squarings
	 * as well as reducing the multiplies.  (It actually doesn't
	 * hurt in the case k = 1, either.)
	 */
	fn oddpowmod(&self, exp: &Integer, modulus: &Integer) -> Integer {
		/* Special case for exponent of one */
		if exp.compare(&Integer::one()) == Ordering::Equal {
			return self.clone();
		}

		/* Special case for base of zero */
		if self.sign == 0 {
			return Integer::zero();
		}

		/* initialize magnitudes for calculating */
		let mut a = self.shift_left(modulus.len << 6);

		/* Look up appropriate k-1 for the exponent - tblmask = 1<<(k-1) */
		let (mut wbits, mut ebits) = (0, exp.bitlen as i32);
		if (ebits != 17) || (exp.data[0] != 0x10001) {
			while ebits > BNEXPMOD_THRESHOLD[wbits] {
				wbits += 1;
			}
		} // if exponent is 65537 (0x10001), use minimum window size

		/* calculate appropriate table size */
		let tblmask = 1 << wbits;

		/* allocate table for precomputed odd powers of base in Montgomery form */
		let mut table = vec![Integer::zero(); tblmask];

		/* compute the modular inverse */
		let inv: i64 = -(mod_inverse64(modulus.data[0]) as i64);

		/* compute table[0] */
		let DivideResult(_, mut r) = a.divide_with(modulus);
		r.len = r.size;
		table[0] = r;

		/* set b to the square of the base */
		let mut b = table[0].square();
		if b.size < 2 * modulus.len {
			b.resize(2 * modulus.len);
		}
		b.len = 2 * modulus.len;
		b = Integer::mont_reduce(&b, modulus, inv as u64);
		b.len = b.size;

		/* use high half of b to initialize the table */
		let t = b.get_slice(b.len - modulus.len, modulus.len);
		for i in 1..tblmask {
			let mut prod = t.multiply_with(&table[i - 1]);
			if prod.size < 2 * modulus.len {
				prod.resize(2 * modulus.len);
			}
			prod.len = 2 * modulus.len;
			prod = Integer::mont_reduce(&prod, modulus, inv as u64);
			prod.len = prod.size;
			table[i] = prod;
		}

		/* Initialze the fetch pointer */
		let mut bitpos = 1u64 << ((ebits as usize - 1) & (BLOCK_BIT - 1)); /* Initialize mask */

		/* pre load the window that slides over the exponent */
		let (mut buf, mut elen, mut eindex) = (0, exp.len, exp.len - 1);
		for _ in 0..=wbits {
			buf = (buf << 1) | ((exp.data[eindex] & bitpos) != 0) as usize;
			bitpos >>= 1;
			if bitpos == 0 {
				eindex -= 1;
				bitpos = 1 << (BLOCK_BIT - 1);
				elen -= 1;
			}
		}

		assert!(buf & tblmask > 0); // highest bit is 1

		/* The first iteration, which is hoisted out of the main loop */
		ebits -= 1;
		let mut isone = true;

		let mut multpos = ebits - wbits as i32;
		while (buf & 1) == 0 {
			buf >>= 1;
			multpos += 1;
		}
		/* Intermediates can wrap, but final must NOT */
		assert!(multpos <= ebits);
		let mut mult = &table[buf >> 1]; // uses for multiply only.
		buf = 0;

		/* Special case: use already-computed value sitting in buffer */
		if multpos == ebits {
			isone = false;
		}

		/*
		 * The main loop.  The procedure is:
		 * - Advance the window
		 * - If the most-significant bit of the window is set,
		 *   schedule a multiply for the appropriate time in the
		 *   future (may be immediately)
		 * - Perform any pending multiples
		 * - Check for termination
		 * - Square the buffer
		 *
		 * At any given time, the acumulated product is held in
		 * the high half of b.
		 */
		loop {
			ebits -= 1;
			/* Advance the window */
			assert!(buf < tblmask);
			buf <<= 1;
			/*
				* This reads ahead of the current exponent position
				* (controlled by ebits), so we have to be able to read
				* past the lsb of the exponents without error.
				*/
			if elen > 0 {
				buf |= ((exp.data[eindex] & bitpos) != 0) as usize;
				bitpos >>= 1;
				if bitpos == 0 {
					eindex = eindex.wrapping_sub(1);
					bitpos = 1 << (BLOCK_BIT - 1);
					elen -= 1;
				}
			}

			/* Examine the window for pending multiplies */
			if (buf & tblmask) != 0 {
				multpos = ebits - wbits as i32;
				while (buf & 1) == 0 {
					buf >>= 1;
					multpos += 1;
				}
				/* Intermediates can wrap, but final must NOT */
				assert!(multpos <= ebits);
				mult = &table[buf >> 1];
				buf = 0;
			}

			/* If we have a pending multiply, do it */
			if ebits == multpos {
				if isone {
					/* Multiply by 1 is a trivial case */
					b = mult.clone();
					isone = false;
				} else {
					/* Multiply by the table entry remembered previously */
					a = b.multiply_with(mult);
					if a.size < 2 * modulus.len {
						a.resize(2 * modulus.len);
					}
					a.len = 2 * modulus.len;
					a = Integer::mont_reduce(&a, modulus, inv as u64);
					a.len = a.size;
					/* Swap a and b */
					let tmp = a;
					a = b;
					b = tmp;
				}
			}

			/* Are we done? */
			if ebits == 0 {
				break;
			}

			/* Square the input */
			if !isone {
				a = b.square();
				if a.size < 2 * modulus.len {
					a.resize(2 * modulus.len);
				}
				a.len = 2 * modulus.len;
				a = Integer::mont_reduce(&a, modulus, inv as u64);
				a.len = a.size;
				/* Swap a and b */
				let tmp = a;
				a = b;
				b = tmp;
			}
		} /* !loop */

		/* Convert result out of Montgomery form */
		b.resize(2 * modulus.len);
		b.len = b.size;
		b = Integer::mont_reduce(&b, modulus, inv as u64);
		b.sign = 1;
		b.regularize();
		b
	}

	fn mod_inverse(&self, rhs: &Integer) -> Integer {
		assert!(rhs.sign > 0);
		if rhs.compare(&Integer::one()) == Ordering::Equal {
			return Integer::zero();
		}
		let base = match self.sign < 0 || self.compare(rhs) >= Ordering::Equal {
			true => self.divide_with(rhs).1,
			false => self.clone(),
		};

		/* Modulus is odd, use Schroeppel's algorithm */
		if (rhs.data[0] & 1) == 1 {
			return base.mod_inverse_odd(rhs);
		}

		/* get even part of modulus expressed as a power of 2 */
		let p: i32 = rhs.num_of_trailing_zero() as i32;
		let oddm = rhs.shift_right(p as usize);

		if oddm.compare(&Integer::one()) == Ordering::Equal {
			return base.mod_inverse_k(p);
		}

		/* calculate 1/a mod oddMod */
		let odd_part = base.mod_inverse_odd(&oddm);

		/* Calculate 1/a mod evenMod */
		let even_part = base.mod_inverse_k(p);

		// Combine the results using Chinese Remainder Theorem
		let y1 = Integer::fixup_reciprocal(&Integer::one(), &oddm, p as u32);
		let y2 = oddm.mod_inverse_k(p);

		let res = odd_part
			.shift_left(p as usize)
			.multiply_with(&y1)
			.add_with(&even_part.multiply_with(&oddm).multiply_with(&y2));
		res.divide_with(rhs).1
	}

	fn mod_inverse_k(&self, k: i32) -> Integer {
		assert!(self.sign > 0);
		if self.data[0] & 1 == 0 {
			panic!("the integer is not invertible since the modulus and value is not relatively prime.")
		} // gcd(num, 2^k) == 1
		match k {
			0..=64 => Integer::try_convert(mod_inverse64(self.data[0]) & ((1u64 << k) - 1), 1),
			65..=128 => Integer::try_convert(
				mod_inverse128(((self.data[1] as u128) << 64) + self.data[0] as u128)
					& ((1u128 << k) - 1),
				1,
			),
			_ => {
				/* extended Euclidean algorithm */
				let (mut t, mut newt) = (Integer::zero(), Integer::one());
				let (mut r, mut newr) = (newt.shift_left(k as usize), self.clone());

				while newr.sign != 0 {
					let DivideResult(quo, rem) = r.divide_with(&newr);
					let tmp = t.subtract_with(&quo.multiply_with(&newt));
					t = newt;
					newt = tmp;
					r = newr;
					newr = rem;
				}
				assert!(r.compare(&Integer::one()) <= Ordering::Equal);
				t
			}
		}
	}

	/* The Almost Inverse Algorithm
	 * Initialize integer k=O, and polynomials B=l,C=O,F=A,G=M.
	 * loop: While F is even, do F=F/er, C=C*u, k=k+i.
	 * If F = 1, then return B,k.
	 * If deg(F) < deg(G), then exchange F,G and exchange B,C.
	 * F=F+G , B=B+C . Goto loop.
	 * Schroeppel, Richard, et al. "Fast key exchange with elliptic curve systems."
	 */
	fn mod_inverse_odd(&self, rhs: &Integer) -> Integer {
		let mut k = 0usize;
		let (mut b, mut c, mut f, mut g) =
			(Integer::one(), Integer::zero(), self.clone(), rhs.clone());

		loop {
			/* Right shift f k times until odd, left shift c k times */
			if (f.data[0] & 1) == 0 {
				let i = f.num_of_trailing_zero();
				f.fshr(i);
				c = c.shift_left(i);
				k += i;
			}

			assert!(f.sign != 0);

			if f.sign == 1 && f.bitlen == 1 {
				break;
			} /* f == 1 */

			/* If f < g exchange f, g and b, c */
			if f.compare(&g) < Ordering::Equal {
				let tmp = f;
				f = g;
				g = tmp;
				let tmp = b;
				b = c;
				c = tmp;
			}

			/* if f == g (mod 4), subtracts instead of adds */
			if (f.data[0] ^ g.data[0]) & 3 == 0 {
				f = f.subtract_with(&g);
				b = b.subtract_with(&c);
			} else {
				f = f.add_with(&g);
				b = b.add_with(&c);
			}
		}

		while b.sign < 0 {
			b = b.add_with(&rhs);
		}
		Integer::fixup_reciprocal(&b, &rhs, k as u32)
	}

	/* Given c, k, and prime p, where a*c == 2**k (mod p),
	 * Compute x = (a ** -1) mod p.  This is similar to Montgomery reduction.
	 * This technique from the paper "Fast Modular Reciprocals" (unpublished)
	 * by Richard Schroeppel.
	 */
	fn fixup_reciprocal(c: &Integer, p: &Integer, k: u32) -> Integer {
		let r = -(mod_inverse64(p.data[0]) as i64);
		let mut pc = c.clone();
		for _ in 0..(k >> 5) {
			// V = R * c (mod 2^j)
			let v = r * (pc.data[0] as i64);
			// c = c + (v * p)
			pc = pc.add_with(&Integer::try_convert(v.abs(), v as isize).multiply_with(p)); // invalidate
																			   // c = c / 2^j
			pc.fshr(BLOCK_BIT);
		}

		let num_bits = k & 0x3f;
		if num_bits != 0 {
			// V = R * c (mod 2^j)
			let mut v = r * (pc.data[0] as i64);
			v &= (1 << num_bits) - 1;
			// c = c + (v * p)
			pc = pc.add_with(&Integer::try_convert(v.abs(), v as isize).multiply_with(p));
			// c = c / 2^j
			pc.fshr(num_bits as usize);
		}

		// In theory, c may be greater than p at this point (Very rare!)
		while pc.compare(p) >= Ordering::Equal {
			pc = pc.subtract_with(p);
		}
		pc
	}
	/* Montgomery reduce n, modulo mod. Note: n will be changed in the progress */
	fn mont_reduce(n: &Integer, modulus: &Integer, inv: u64) -> Integer {
		assert!(n.len == 2 * modulus.len);
		let mut pn = n.clone();
		pn.resize(n.len + 1);
		let mut mont_data = vec![0u64; modulus.len + 1];
		montgomery_reduce(
			&mut mont_data,
			&mut pn.data,
			&modulus.data[..modulus.len],
			inv,
		);
		mont_data.truncate(modulus.len);
		let mut res = Integer {
			sign: n.sign,
			bitlen: 0,
			len: modulus.len,
			size: modulus.len,
			hook: 0,
			data: mont_data,
		};
		res.regularize();
		res
	}

	fn sieve_retrieve(&self, sieve: Sieve, precision: i32) -> Option<Integer> {
		// Examine the sieve one long at a time to find possible primes
		sieve[0..sieve.size()]
			.into_par_iter()
			.enumerate()
			.find_map_any(|params| {
				let (idx, n) = params;
				let mut next = *n ^ BLOCK_MAX;
				let mut offset = idx * 2 * BLOCK_BIT + 1;
				for i in 0..BLOCK_BIT {
					if next & 1 == 1 {
						let candidate = self.add_with(&Integer::try_convert(offset, 1));
						if candidate.is_prime(precision) {
							return Some(candidate);
						}
					}
					next >>= 1;
					offset += 2;
				}
				None
			})
	}

	/* Miller-Rabin Probable Prime Test */
	fn passes_miller_rabin(&self, round: i32) -> bool {
		assert!(round > 0 && self.bitlen > 1 && self.is_odd());
		// Find a and m such that m is odd and this == 1 + 2**a * m
		let vm1 = self.subtract_with(&Integer::one());
		let (a, one, two) = (vm1.num_of_trailing_zero(), Integer::one(), Integer::two());
		let m = vm1.shift_right(a);

		// Do the tests
		for _ in 0..round {
			// Generate a uniform random on (1, this)
			let mut b = Integer::random(self.bitlen as u32);
			while b.compare(self) >= Ordering::Equal {
				b = Integer::random(self.bitlen as u32);
			}
			let (mut j, mut z) = (0, b.expmod(&m, self));
			while !(j == 0 && z.eq(&one)) && !z.eq(&vm1) {
				if j > 0 && z.eq(&one) || j == a - 1 {
					return false;
				}
				j += 1;
				z = z.expmod(&two, self);
			}
		}
		true
	}

	/* Lucas-Lehmer probable prime Test
	 * This Integer is a positive, odd number.
	 */
	fn passes_lucas_lehmer(&self) -> bool {
		assert!(self.is_odd() && self.sign > 0);
		let va1 = self.add_with(&Integer::one());

		// step 1
		let mut d: i64 = 5;
		while jacobi(d, &self.data[..self.len]) != -1 {
			d = match d > 0 {
				true => -(d + 2),
				false => -(d - 2),
			};
		}

		// Step 2
		let u = Integer::lucas_sequence(d, &va1, self);

		// Step 3
		let DivideResult(_, rem) = u.divide_with(self);
		rem.eq(&Integer::zero())
	}

	fn lucas_sequence(d: i64, k: &Integer, p: &Integer) -> Integer {
		let d = Integer::try_convert(d.abs(), d as isize);
		let (mut u, mut v) = (Integer::one(), Integer::one());
		let mut u2: Integer;
		let mut v2: Integer;
		for i in (0..k.bitlen - 1).rev() {
			u2 = u.multiply_with(&v).divide_with(&p).1;
			v2 = v
				.square()
				.add_with(&d.multiply_with(&u.square()))
				.divide_with(&p)
				.1;
			if v2.is_odd() {
				v2 = v2.subtract_with(&p);
			}
			v2.fshr(1);

			u = u2;
			v = v2;
			if (k.data[i / BLOCK_BIT] >> (i % BLOCK_BIT)) & 1 == 1 {
				u2 = u.add_with(&v).divide_with(&p).1;
				if u2.is_odd() {
					u2 = u2.subtract_with(&p);
				}
				u2.fshr(1);

				v2 = v.add_with(&d.multiply_with(&u)).divide_with(&p).1;
				if v2.is_odd() {
					v2 = v2.subtract_with(&p);
				}
				v2.fshr(1);

				u = u2;
				v = v2;
			}
		}
		u
	}
}

trait Convert: Sized {
	fn try_convert(num: Self, sign: isize) -> Integer;
}

impl<T: Clone + Sized> Convert for T {
	default fn try_convert(num: Self, sign: isize) -> Integer {
		let sgn: i8 = match sign {
			s if s > 0 => 1,
			0 => 0,
			_ => -1,
		};
		if sgn == 0 {
			return Integer::new(size_of::<T>() * 8);
		}

		let mut val = match size_of::<T>() {
			8 => {
				let num: &u64 = unsafe { transmute(&num) };
				Integer {
					sign: sgn,
					bitlen: 0,
					len: 1,
					size: 1,
					hook: 0,
					data: vec![*num],
				}
			}
			16 => {
				let num: &u128 = unsafe { transmute(&num) };
				Integer {
					sign: sgn,
					bitlen: 0,
					len: 2,
					size: 2,
					hook: 0,
					data: vec![*num as u64, (*num >> 64) as u64],
				}
			}
			n => {
				let raw: *mut u8 = unsafe { transmute(&num) };
				let (vec_size, remains) = ((n + BLOCK_SIZE - 1) / BLOCK_SIZE, n % BLOCK_SIZE);
				let mut vdata = vec![0u64; vec_size];
				let ptr = vdata.as_mut_ptr();
				let ptr_u8: *mut u8 = ptr.cast();
				unsafe { ptr_u8.copy_from(raw, n) }
				Integer {
					sign: sgn,
					bitlen: 0,
					len: vec_size,
					size: vec_size,
					hook: 0,
					data: vdata,
				}
			}
		};
		val.regularize();
		val
	}
}

/* add: a + b */
impl Add for Integer {
	type Output = Integer;

	fn add(self, rhs: Self) -> Integer {
		self.add_with(&rhs)
	}
}

impl Add<&Self> for Integer {
	type Output = Integer;

	fn add(self, rhs: &Self) -> Integer {
		self.add_with(rhs)
	}
}

impl Add<Integer> for &Integer {
	type Output = Integer;

	fn add(self, rhs: Integer) -> Integer {
		self.add_with(&rhs)
	}
}

impl Add for &Integer {
	type Output = Integer;

	fn add(self, rhs: Self) -> Integer {
		self.add_with(rhs)
	}
}

/* add_assign: a += b */
impl AddAssign for Integer {
	fn add_assign(&mut self, rhs: Self) {
		*self = self.add_with(&rhs);
	}
}

impl AddAssign<&Self> for Integer {
	fn add_assign(&mut self, rhs: &Self) {
		*self = self.add_with(rhs);
	}
}

/* sub: a - b */
impl Sub for Integer {
	type Output = Integer;

	fn sub(self, rhs: Self) -> Integer {
		self.subtract_with(&rhs)
	}
}

impl Sub<&Self> for Integer {
	type Output = Integer;

	fn sub(self, rhs: &Self) -> Integer {
		self.subtract_with(rhs)
	}
}

impl Sub<Integer> for &Integer {
	type Output = Integer;

	fn sub(self, rhs: Integer) -> Integer {
		self.subtract_with(&rhs)
	}
}

impl Sub for &Integer {
	type Output = Integer;

	fn sub(self, rhs: Self) -> Integer {
		self.subtract_with(rhs)
	}
}

/* sub_assign: a -= b */
impl SubAssign for Integer {
	fn sub_assign(&mut self, rhs: Self) {
		*self = self.subtract_with(&rhs);
	}
}

impl SubAssign<&Self> for Integer {
	fn sub_assign(&mut self, rhs: &Self) {
		*self = self.subtract_with(rhs);
	}
}

/* mul: a * b */
impl Mul for Integer {
	type Output = Integer;

	fn mul(self, rhs: Self) -> Integer {
		self.multiply_with(&rhs)
	}
}

impl Mul<&Self> for Integer {
	type Output = Integer;

	fn mul(self, rhs: &Self) -> Integer {
		self.multiply_with(rhs)
	}
}

impl Mul<Integer> for &Integer {
	type Output = Integer;

	fn mul(self, rhs: Integer) -> Integer {
		self.multiply_with(&rhs)
	}
}

impl Mul for &Integer {
	type Output = Integer;

	fn mul(self, rhs: Self) -> Integer {
		self.multiply_with(rhs)
	}
}

/* mul_assign: a *= b */
impl MulAssign for Integer {
	fn mul_assign(&mut self, rhs: Self) {
		*self = self.multiply_with(&rhs);
	}
}

impl MulAssign<&Self> for Integer {
	fn mul_assign(&mut self, rhs: &Self) {
		*self = self.multiply_with(rhs);
	}
}

/* div: a / b */
impl Div for Integer {
	type Output = Integer;

	fn div(self, rhs: Self) -> Integer {
		let DivideResult(quo, _) = self.divide_with(&rhs);
		quo
	}
}

impl Div<&Self> for Integer {
	type Output = Integer;

	fn div(self, rhs: &Self) -> Integer {
		let DivideResult(quo, _) = self.divide_with(rhs);
		quo
	}
}

impl Div<Integer> for &Integer {
	type Output = Integer;

	fn div(self, rhs: Integer) -> Integer {
		let DivideResult(quo, _) = self.divide_with(&rhs);
		quo
	}
}

impl Div for &Integer {
	type Output = Integer;

	fn div(self, rhs: Self) -> Integer {
		let DivideResult(quo, _) = self.divide_with(rhs);
		quo
	}
}

/* div_assign: a /= b */
impl DivAssign for Integer {
	fn div_assign(&mut self, rhs: Self) {
		let DivideResult(quo, _) = self.divide_with(&rhs);
		*self = quo;
	}
}

impl DivAssign<&Self> for Integer {
	fn div_assign(&mut self, rhs: &Self) {
		let DivideResult(quo, _) = self.divide_with(rhs);
		*self = quo;
	}
}

/* rem: a % b */
impl Rem for Integer {
	type Output = Integer;

	fn rem(self, rhs: Self) -> Integer {
		let DivideResult(_, rem) = self.divide_with(&rhs);
		rem
	}
}

impl Rem<&Self> for Integer {
	type Output = Integer;

	fn rem(self, rhs: &Self) -> Integer {
		let DivideResult(_, rem) = self.divide_with(rhs);
		rem
	}
}

impl Rem<Integer> for &Integer {
	type Output = Integer;

	fn rem(self, rhs: Integer) -> Integer {
		let DivideResult(_, rem) = self.divide_with(&rhs);
		rem
	}
}

impl Rem for &Integer {
	type Output = Integer;

	fn rem(self, rhs: Self) -> Integer {
		let DivideResult(_, rem) = self.divide_with(rhs);
		rem
	}
}

/* rem_assign: a %= b */
impl RemAssign for Integer {
	fn rem_assign(&mut self, rhs: Self) {
		let DivideResult(_, rem) = self.divide_with(&rhs);
		*self = rem;
	}
}

impl RemAssign<&Self> for Integer {
	fn rem_assign(&mut self, rhs: &Self) {
		let DivideResult(_, rem) = self.divide_with(rhs);
		*self = rem;
	}
}

impl Index<usize> for Integer {
	type Output = u64;

	fn index<'a>(&'a self, index: usize) -> &'a u64 {
		&self.data[index]
	}
}

impl Index<Range<usize>> for Integer {
	type Output = [u64];

	fn index<'a>(&'a self, index: Range<usize>) -> &'a [u64] {
		&self.data[index.start..index.end]
	}
}

impl Neg for Integer {
	type Output = Integer;

	fn neg(self) -> Integer {
		self.negate()
	}
}

impl Neg for &Integer {
	type Output = Integer;

	fn neg(self) -> Integer {
		self.negate()
	}
}

impl PartialOrd for Integer {
	fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
		Some(self.compare(other))
	}
}

impl PartialOrd<&Self> for Integer {
	fn partial_cmp(&self, other: &&Self) -> Option<Ordering> {
		Some(self.compare(other))
	}
}

impl PartialOrd<Integer> for &Integer {
	fn partial_cmp(&self, other: &Integer) -> Option<Ordering> {
		Some(self.compare(&other))
	}
}

impl PartialEq for Integer {
	fn eq(&self, other: &Self) -> bool {
		self.compare(other) == Ordering::Equal
	}
}

impl PartialEq<&Self> for Integer {
	fn eq(&self, other: &&Self) -> bool {
		self.compare(other) == Ordering::Equal
	}
}

impl PartialEq<Integer> for &Integer {
	fn eq(&self, other: &Integer) -> bool {
		self.compare(&other) == Ordering::Equal
	}
}

impl Shl<usize> for Integer {
	type Output = Integer;

	fn shl(self, rhs: usize) -> Integer {
		self.shift_left(rhs)
	}
}

impl Shl<usize> for &Integer {
	type Output = Integer;

	fn shl(self, rhs: usize) -> Integer {
		self.shift_left(rhs)
	}
}

impl Shr<usize> for Integer {
	type Output = Integer;

	fn shr(self, rhs: usize) -> Integer {
		self.shift_right(rhs)
	}
}

impl Shr<usize> for &Integer {
	type Output = Integer;

	fn shr(self, rhs: usize) -> Integer {
		self.shift_right(rhs)
	}
}

/* power: c = a^k , type(k) = u32 */
impl BitXor<u32> for Integer {
	type Output = Integer;

	fn bitxor(self, rhs: u32) -> Integer {
		self.power(rhs)
	}
}

impl BitXor<u32> for &Integer {
	type Output = Integer;

	fn bitxor(self, rhs: u32) -> Integer {
		self.power(rhs)
	}
}

impl fmt::Display for Integer {
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
		write!(f, "{}", self.decimal())
	}
}

impl fmt::Debug for Integer {
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
		write!(f, "{}", self.hex())
	}
}
